Over 40 years ago, Karp, Upfal, and Wigderson initiated the study of a fundamental question in parallel computation: how many adaptive rounds are required to find a basis of a matroid using only polynomially many independence queries (that is, queries that test whether a set is independent)? Their pioneering work established an upper bound of O(\sqrt{n}) rounds and a lower bound of roughly n^{1/3} rounds; these bounds have remained unchanged since.
In this talk, I will present recent progress on this question. We give a new parallel algorithm that, with high probability, finds a matroid basis in ~O(n^{3/7}) rounds, improving upon the classical O(\sqrt{n}) bound. For the important special case of partition matroids, we obtain an optimal ~O(n^{1/3}) round algorithm, essentially settling the round complexity in this setting. Our approach introduces a new matroid decomposition technique that may be of independent interest and also yields faster parallel algorithms for the classic matroid intersection problem.
This is joint work with Sanjeev Khanna and Junkai Song (NYU).